{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #4Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fourSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #四数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由 <code>n</code> 个整数组成的数组&nbsp;<code>nums</code> ，和一个目标值 <code>target</code> 。请你找出并返回满足下述全部条件且<strong>不重复</strong>的四元组&nbsp;<code>[nums[a], nums[b], nums[c], nums[d]]</code>&nbsp;（若两个四元组元素一一对应，则认为两个四元组重复）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= a, b, c, d&nbsp;&lt; n</code></li>\n",
    "\t<li><code>a</code>、<code>b</code>、<code>c</code> 和 <code>d</code> <strong>互不相同</strong></li>\n",
    "\t<li><code>nums[a] + nums[b] + nums[c] + nums[d] == target</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以按 <strong>任意顺序</strong> 返回答案 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,0,-1,0,-2,2], target = 0\n",
    "<strong>输出：</strong>[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,2,2,2,2], target = 8\n",
    "<strong>输出：</strong>[[2,2,2,2]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 200</code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= target &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [4sum](https://leetcode.cn/problems/4sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [4sum](https://leetcode.cn/problems/4sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,-1,0,-2,2]\\n0', '[2,2,2,2,2]\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "  def fourSumCount(self, A, B, C, D):\n",
    "    \"\"\" \n",
    "    :type A: List[int]\n",
    "    :type B: List[int]\n",
    "    :type C: List[int]\n",
    "    :type D: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    abCount = Counter( ( a + b ) for a in A for b in B )\n",
    "    cdCount = Counter( ( c + d ) for c in C for d in D )\n",
    "\n",
    "    n = 0\n",
    "    for ab in abCount:\n",
    "      if -ab in cdCount:\n",
    "        n += abCount[ ab ] * cdCount[ -ab ]\n",
    "\n",
    "    return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        \n",
    "        # checkup = collections.defaultdict(int)\n",
    "        # n = len(nums1)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(n):\n",
    "        #         if checkup[nums1[i]+nums2[j]] == 0 :\n",
    "        #             checkup[nums1[i]+nums2[j]]=1\n",
    "        #         else:\n",
    "        #             checkup[nums1[i]+nums2[j]]+=1\n",
    "        countAB = collections.Counter(u + v for u in nums1 for v in nums2)\n",
    "        \n",
    "        ans = 0\n",
    "        for u in nums3:\n",
    "            for v in nums4:\n",
    "                if -u -v in countAB:\n",
    "                    ans += countAB[-u-v]\n",
    "        return ans\n",
    "        \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        record = dict()\n",
    "        times = 0\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in record:\n",
    "                    record[i+j] += 1\n",
    "                else:\n",
    "                    record[i+j] = 1\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                key = 0 - i - j\n",
    "                if key in record:\n",
    "                    times += record[key]\n",
    "        return times\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1, nums2, nums3, nums4) -> int:\n",
    "        n = len(nums1)\n",
    "        ans = 0\n",
    "        count = dict()\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                t = nums1[i] + nums2[j]\n",
    "                if t not in count:\n",
    "                    count[t] = 0\n",
    "                count[t] += 1\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                x = nums3[i] + nums4[j]\n",
    "                if -x in count:\n",
    "                    ans += count[-x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        record = {}\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                if n1 + n2 in record:\n",
    "                    record[n1 + n2] += 1\n",
    "                else:\n",
    "                    record[n1 + n2] = 1\n",
    "        count = 0\n",
    "        for n3 in nums3:\n",
    "            for n4 in nums4:\n",
    "                if - n3 - n4 in record:\n",
    "                    count += record[- n3 - n4]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        n1=dict()\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in n1.keys():\n",
    "                    n1[i+j]=n1[i+j]+1\n",
    "                else:\n",
    "                    n1[i+j]=1\n",
    "        n2=dict()\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                if i+j in n2.keys():\n",
    "                    n2[i+j]=n2[i+j]+1\n",
    "                else:\n",
    "                    n2[i+j]=1\n",
    "        s=0\n",
    "        for i in n1.keys():\n",
    "            for j in n2.keys():\n",
    "                if i+j==0:\n",
    "                    s=s+n1[i]*n2[j]\n",
    "        print(n1,n2)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        rec, cnt = defaultdict(lambda : 0), 0\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                rec[i+j] += 1\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                cnt += rec.get(-(i+j), 0) \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        dic = dict()\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in dic:\n",
    "                    dic[i+j]+=1\n",
    "                else:\n",
    "                    dic[i+j] = 1\n",
    "        \n",
    "        count = 0\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                if -i-j in dic:\n",
    "                    count+=dic[-i-j]\n",
    "        \n",
    "\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "\n",
    "        hashmap = dict()\n",
    "\n",
    "        for i in nums1:\n",
    "            for j in nums2:\n",
    "                if i+j in hashmap:\n",
    "                   hashmap[i+j] += 1\n",
    "                else:\n",
    "                    hashmap[i+j] = 1\n",
    "        \n",
    "        count = 0\n",
    "        for i in nums3:\n",
    "            for j in nums4:\n",
    "                index = -i-j\n",
    "                if index in hashmap:\n",
    "                    count += hashmap[index]\n",
    "        return count\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:\n",
    "        # 使用字典存储nums1和nums2中的元素及其和\n",
    "        hashmap = dict()\n",
    "        for n1 in nums1:\n",
    "            for n2 in nums2:\n",
    "                if n1 + n2 in hashmap:\n",
    "                    hashmap[n1 + n2] += 1\n",
    "                else:\n",
    "                    hashmap[n1 + n2] = 1\n",
    "\n",
    "        # 如果 -(n1+n2) 存在于nums3和nums4, 存入结果\n",
    "        count = 0\n",
    "        for n3 in nums3:\n",
    "            for n4 in nums4:\n",
    "                key = -(n3 + n4)\n",
    "                if key in hashmap:\n",
    "                    count += hashmap[key]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "  def fourSum(self, nums, target):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :type target: int\n",
    "    :rtype: List[List[int]]\n",
    "    \"\"\"\n",
    "    twoSum = defaultdict( list )\n",
    "    for i in range( len( nums ) - 1 ):\n",
    "      for j in range( i + 1, len( nums ) ):\n",
    "        twoSum[ nums[i] + nums[j] ].append( (i, j) )\n",
    "\n",
    "    ans = set()\n",
    "    for abSum in twoSum:\n",
    "      cdSum = target - abSum\n",
    "      if cdSum not in twoSum:\n",
    "        continue\n",
    "\n",
    "      for a, b in twoSum[ abSum ]:\n",
    "        for c, d in twoSum[ cdSum ]:\n",
    "          if len( { a, b, c, d } ) == 4:\n",
    "            ans.add( tuple(sorted(( nums[a], nums[b], nums[c], nums[d] ))) )\n",
    "\n",
    "    return [ list(t) for t in ans ]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        numsLen=len(nums)\n",
    "        ans=[]\n",
    "        for i in range(numsLen-3):\n",
    "            for j in range(i+1,numsLen): #3 sum\n",
    "                s=j+1\n",
    "                e=len(nums)-1\n",
    "                while s<e:\n",
    "                    sum=nums[i]+nums[j]+nums[s]+nums[e]\n",
    "                    if sum==target:\n",
    "                        list=[nums[i],nums[j],nums[s],nums[e]]\n",
    "                        if list not in ans:\n",
    "                            ans.append(list)\n",
    "                        s+=1\n",
    "                        e-=1\n",
    "                    elif sum<target:\n",
    "                        s+=1\n",
    "                    else:\n",
    "                        e-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        if len(nums) < 4:\n",
    "            return []\n",
    "\n",
    "        nums = sorted(nums)\n",
    "        outs = []\n",
    "        i = 0\n",
    "        while i < len(nums) - 3:\n",
    "            j = len(nums) - 1\n",
    "\n",
    "            while j > i + 2:\n",
    "                k = i + 1\n",
    "                w = j - 1\n",
    "                while k < w:\n",
    "                    sums = nums[i] + nums[j] + nums[k] + nums[w]\n",
    "                    if sums < target:\n",
    "                        k += 1\n",
    "                    elif sums > target:\n",
    "                        w -= 1\n",
    "                    else:\n",
    "                        outs.append([nums[i], nums[k], nums[w], nums[j]])\n",
    "                        k += 1\n",
    "                        w -= 1\n",
    "                        while k < w and nums[k] == nums[k - 1]:\n",
    "                            k += 1\n",
    "                        while k < w and nums[w] == nums[w + 1]:\n",
    "                            w -= 1\n",
    "\n",
    "                j -= 1\n",
    "                while j > i + 2 and nums[j] == nums[j + 1]:\n",
    "                    j -= 1\n",
    "            i += 1\n",
    "            while i < len(nums) - 3 and nums[i - 1] == nums[i]:\n",
    "                i += 1\n",
    "        return outs\n",
    "\n",
    "\n",
    "s = Solution()\n",
    "# print(s.fourSum([1, 0, -1, 0, -2, 2], 0))\n",
    "print(s.fourSum([-3, -1, 0, 2, 4, 5], 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "\n",
    "        def findNsum(l, r, target, N, result, results):\n",
    "            if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:  # early termination\n",
    "                return\n",
    "            if N == 2: # two pointers solve sorted 2-sum problem\n",
    "                while l < r:\n",
    "                    s = nums[l] + nums[r]\n",
    "                    if s == target:\n",
    "                        results.append(result + [nums[l], nums[r]])\n",
    "                        l += 1\n",
    "                        r -= 1\n",
    "                        while l < r and nums[l] == nums[l - 1]:\n",
    "                            l += 1\n",
    "                        while r > l and nums[r] == nums[r + 1]:\n",
    "                            r -= 1\n",
    "                    elif s < target:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "            else: # recursively reduce N\n",
    "                for i in range(l, r+1):\n",
    "                    if i == l or (i > l and nums[i-1] != nums[i]):\n",
    "                        findNsum(i+1, r, target-nums[i], N-1, result+[nums[i]], results)\n",
    "\n",
    "        nums.sort()\n",
    "        results = []\n",
    "        findNsum(0, len(nums)-1, target, 4, [], results)\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        for i in range(len(nums) - 3):\n",
    "            if i and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            for j in range(i + 1, len(nums) - 2):\n",
    "                if j != i + 1 and nums[j] == nums[j - 1]:\n",
    "                    continue\n",
    "                sum = target - nums[i] - nums[j]\n",
    "                left, right = j + 1, len(nums) - 1\n",
    "                while left < right:\n",
    "                    if nums[left] + nums[right] == sum:\n",
    "                        res.append([nums[i], nums[j], nums[left], nums[right]])\n",
    "                        right -= 1\n",
    "                        left += 1\n",
    "                        while left < right and nums[left] == nums[left - 1]:\n",
    "                            left += 1\n",
    "                        while left < right and nums[right] == nums[right + 1]:\n",
    "                            right -= 1\n",
    "                    elif nums[left] + nums[right] > sum:\n",
    "                        right -= 1\n",
    "                    else:\n",
    "                        left += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        #这种求和为了减少步骤首先是排序比较  哎哎哎\n",
    "        a = nums[:4]\n",
    "        if sum(nums[:4]) > target:\n",
    "            return res\n",
    "        for index, num in enumerate(nums[:-3]):\n",
    "            target1 = target - num\n",
    "            if sum(nums[index: index + 4]) > target:\n",
    "                break\n",
    "                #下面的条件是最后的三个数比target1还小就是在target1固定的情况下达不到目标了\n",
    "                #或者是我现在的数和我上一次的数相同  确实 这种情况下不进行下一个循环就会重复\n",
    "                #记住 这个条件总的就是 要么达不到 要么会重复所以跳过\n",
    "            elif sum(nums[-3:]) < target1 or (index > 0 and num == nums[index - 1]):\n",
    "                continue\n",
    "                #在固定第一个后第二个数进行循环 因为是四个数所以截止到倒数第三个\n",
    "            for j in range(index + 1, len(nums) - 2):\n",
    "                target2 = target1 - nums[j]\n",
    "                #同样的道理 两种情况剔除\n",
    "                if nums[j + 1] + nums[j + 2] > target2:\n",
    "                    break\n",
    "                elif nums[-2] + nums[-1] < target2 or (j > index + 1 and nums[j] == nums[j - 1]):\n",
    "                    continue\n",
    "                    #再把特殊情况剔除后达到我们最后两个数的和等于目标  用双指针法  但为什么这么写会快很多啊 不是很懂 ：（\n",
    "                l, r = j + 1, len(nums) - 1\n",
    "                while l < r:\n",
    "                    temp = nums[l] + nums[r]\n",
    "                    if temp > target2:\n",
    "                        r -= 1\n",
    "                    elif temp < target2:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        res.append([num, nums[j], nums[l], nums[r]])\n",
    "                        while l < r and nums[l] == nums[l + 1]:\n",
    "                            l += 1\n",
    "                        while l < r and nums[r] == nums[r - 1]:\n",
    "                            r -= 1\n",
    "                        #相等之后确实两面都要移  不然会重复 因为这两个数相等的结果都有了\n",
    "                        l += 1\n",
    "                        r -= 1\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        result = []\n",
    "        for i in range(len(nums)):\n",
    "            if i != 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if j != i+1 and nums[j] == nums[j-1]:\n",
    "                    continue\n",
    "                l = j + 1\n",
    "                r = len(nums)-1\n",
    "                while l < r:\n",
    "                    s = nums[i] + nums[j] + nums[l] + nums[r]\n",
    "                    if s == target:\n",
    "                        result.append([nums[i],nums[j],nums[l],nums[r]])\n",
    "                        l += 1\n",
    "                        r -= 1\n",
    "                        while l < r and nums[l-1] == nums[l]:\n",
    "                            l += 1\n",
    "                        while l < r and nums[r+1] == nums[r]:\n",
    "                            r -= 1\n",
    "                    elif s < target:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "        return result\n",
    "                            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        nums.sort()\n",
    "        print('#')\n",
    "        for i in range(len(nums)-3):\n",
    "            print(i)\n",
    "            # if nums[i]==nums[i+1]:continue\n",
    "            for j in range(i+1,len(nums)-2):\n",
    "                # if nums[j]==nums[j+1]:continue\n",
    "                l=j+1;r=len(nums)-1;\n",
    "                while(l<r):\n",
    "                    sum=nums[i]+nums[j]+nums[l]+nums[r]\n",
    "                    if sum==target:\n",
    "                        ans=[nums[i],nums[j],nums[l],nums[r]]\n",
    "                        if ans not in res:\n",
    "                            res.append(ans)\n",
    "                        l+=1\n",
    "                        r-=1\n",
    "                    elif sum<target:\n",
    "                        l+=1\n",
    "                    else:\n",
    "                        r-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef fourSum(self, nums: 'list[int]', \n",
    "\ttarget: 'int') -> 'list[list[int]]':\n",
    "\t\t\n",
    "\t\tle = len(nums)\n",
    "\t\tif le < 4: return []\n",
    "\t\t\n",
    "\t\tquater = target / 4\n",
    "\t\tnums.sort()\n",
    "\t\tif nums[0] > quater or nums[-1] < quater : return []\n",
    "\t\t\n",
    "\t\t'''Find all possible [i1, i4] in outers'''\n",
    "\t\touters = []\n",
    "\t\tfor i1 in range(le - 3):\n",
    "\t\t\tn1 = nums[i1]\n",
    "\t\t\ttry:\n",
    "\t\t\t\tif i1 != 0 and n1 == nums[i1 - 1]: continue\n",
    "\t\t\texcept IndexError: pass\n",
    "\t\t\t\n",
    "\t\t\tfor i4_ in range(le - i1 - 3):\n",
    "\t\t\t\ti4 = le - i4_ - 1\n",
    "\t\t\t\tn4 = nums[i4]\n",
    "\t\t\t\ttry:\n",
    "\t\t\t\t\tif i4 != le - 1 and n4 == nums[i4 + 1]: continue\n",
    "\t\t\t\t\touters.append([i1, i4])\n",
    "\t\t\t\texcept IndexError: pass\n",
    "\t\t\t\t\t\t\n",
    "\t\tres = []\n",
    "\t\tfor [i1, i4] in outers:\n",
    "\t\t\tn1, n4 = nums[i1], nums[i4]\n",
    "\t\t\t'''continueing iteration coditions:'''\n",
    "\t\t\tif n1 > quater or n4 < quater: continue\n",
    "\t\t\t\t\n",
    "\t\t\t'''Inner iteration:\n",
    "\t\t\t   Search in nums[i1 + 1: i4] for i2, i3 for\n",
    "\t\t\t   n2 + n3 = target - n1 - n4\n",
    "\t\t\t'''\n",
    "\t\t\ti2 = i1 + 1\n",
    "\t\t\ti3 = i4 - 1\n",
    "\t\t\twhile i2 < i3:\n",
    "\t\t\t\ttry:\n",
    "\t\t\t\t\tn2, n3 = nums[i2], nums[i3]\n",
    "\t\t\t\t\tinner_target = target - n1 - n4\n",
    "\t\t\t\t\tif n2 + n3 < inner_target:\n",
    "\t\t\t\t\t\ti2 += 1\n",
    "\t\t\t\t\t\twhile nums[i2] == nums[i2 - 1]: i2 += 1\n",
    "\t\t\t\t\telif n2 + n3 > inner_target:\n",
    "\t\t\t\t\t\ti3 -= 1\n",
    "\t\t\t\t\t\twhile nums[i3] == nums[i3 + 1]: i3 -= 1\n",
    "\t\t\t\t\telse:\n",
    "\t\t\t\t\t\tres.append([n1, n2, n3, n4])\n",
    "\t\t\t\t\t\ti2 += 1\n",
    "\t\t\t\t\t\twhile nums[i2] == nums[i2 - 1]: i2 += 1\n",
    "\t\t\t\t\t\ti3 -= 1\n",
    "\t\t\t\t\t\twhile nums[i3] == nums[i3 + 1]: i3 -= 1\n",
    "\t\t\t\texcept IndexError: continue\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        result = set()\n",
    "        sum_of_two = {}\n",
    "        len_of_nums = len(nums)\n",
    "        if len_of_nums<4:\n",
    "            return []\n",
    "        sum_ij_min = nums[0] + nums[1]\n",
    "        sum_ij_threshold = target - sum_ij_min\n",
    "        sum_of_two[sum_ij_min] = [[0,1]]\n",
    "        for i in range(len_of_nums):\n",
    "            for j in range(i+1,len_of_nums):\n",
    "                if i==0 and j==1:\n",
    "                    continue\n",
    "                sum_ij = nums[i]+nums[j]\n",
    "                if sum_ij > sum_ij_threshold:\n",
    "                    break\n",
    "                key_list = sum_of_two.keys()\n",
    "                if sum_ij not in key_list:\n",
    "                    sum_of_two[sum_ij] = [[i,j]]\n",
    "                else:\n",
    "                    sum_of_two[sum_ij].append([i,j])\n",
    "                if target-sum_ij in key_list:\n",
    "                    for xy in sum_of_two[target-sum_ij]:\n",
    "                        if i not in xy and j not in xy:\n",
    "                            result.add(tuple(sorted([nums[xy[0]],nums[xy[1]],nums[i],nums[j]])))\n",
    "        return list(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if len(nums) < 4:\n",
    "            return []\n",
    "        \n",
    "        def twoSum(nums,x1,x2):\n",
    "            t = target-(x1+x2)\n",
    "            left_added = set()\n",
    "            l,r = 0,len(nums)-1\n",
    "            result = []\n",
    "            while r > l:\n",
    "                if nums[l]+nums[r] == t:\n",
    "                    if nums[l] not in left_added:\n",
    "                        left_added.add(nums[l])\n",
    "                        result.append([x1,x2,nums[l],nums[r]])\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                elif nums[l]+nums[r] > t:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "            return result\n",
    "        \n",
    "        nums.sort()\n",
    "        x12_record = []\n",
    "        result = []\n",
    "        for i in range(len(nums)-3):\n",
    "            for j in range(i+1,len(nums)-2):\n",
    "                if [nums[i],nums[j]] not in x12_record:\n",
    "                    x12_record.append([nums[i],nums[j]])\n",
    "                    for fourple in twoSum(nums[j+1:],nums[i],nums[j]):\n",
    "                        result.append(fourple)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        if len(nums) < 4:\n",
    "            return []\n",
    "        nums, d, numc = self.prebuild(nums, target)\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            a = nums[i]\n",
    "            numc[a] -= 1\n",
    "            for j in range(i, len(nums)):\n",
    "                b = nums[j]\n",
    "                if numc[b] > 0:\n",
    "                    numc[b] -= 1\n",
    "                    l = self.binsearch(nums, numc, d, target - a - b, b)\n",
    "                    for each in l:\n",
    "                        ans.append([a,b,each[0],each[1]])\n",
    "                    numc[b] += 1\n",
    "            numc[a] += 1\n",
    "        return ans\n",
    "    \n",
    "    def prebuild(self, nums, target):\n",
    "        nums.sort()\n",
    "        # 剔除太小或太大的数\n",
    "        l = 0\n",
    "        r = len(nums)\n",
    "        unfinish = True\n",
    "        while unfinish:\n",
    "            unfinish = False\n",
    "            while r - l > 3:\n",
    "                if nums[l] + nums[r-1] + nums[r-2] + nums[r-3] < target:\n",
    "                    l += 1\n",
    "                    unfinish = True\n",
    "                else:\n",
    "                    break\n",
    "            while r - l > 3:\n",
    "                if nums[r-1] + nums[l] + nums[l+1] + nums[l+2] > target:\n",
    "                    r -= 1\n",
    "                    unfinish = True\n",
    "                else:\n",
    "                    break\n",
    "        nums = nums[l:r]\n",
    "        if len(nums) < 4:\n",
    "            return [], dict(), []\n",
    "\n",
    "        numc = dict()\n",
    "        uninums = []\n",
    "        tmp = nums[0]\n",
    "        for each in nums:\n",
    "            if tmp != each:\n",
    "                uninums.append(tmp)\n",
    "                tmp = each\n",
    "            numc[tmp] = numc.get(tmp, 0) + 1\n",
    "        uninums.append(tmp)\n",
    "        d = dict()\n",
    "        for i in range(len(uninums)):\n",
    "            a = uninums[i]\n",
    "            numc[a] -= 1\n",
    "            for j in range(i, len(uninums)):\n",
    "                b = uninums[j]\n",
    "                if numc[b] > 0:\n",
    "                    n = a + b\n",
    "                    l = d.get(n, [])\n",
    "                    l.append((a, b))\n",
    "                    d[n] = l\n",
    "            numc[a] += 1\n",
    "        return uninums, d, numc\n",
    "        \n",
    "    def binsearch(self, nums, numc, d, target, ge):\n",
    "        t = d.get(target, [])\n",
    "        if len(t) == 0:\n",
    "            return []\n",
    "        l = 0\n",
    "        r = len(t)\n",
    "        ans = None\n",
    "        while l <= r and l < len(t):\n",
    "            m = int((l + r) / 2)\n",
    "            if t[m][0] >= ge:\n",
    "                r = m - 1\n",
    "                ans = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        l = []\n",
    "        if ans is not None:\n",
    "            for i in range(ans, len(t)):\n",
    "                c = t[i][0]\n",
    "                d = t[i][1]\n",
    "                numc[c] -= 1\n",
    "                numc[d] -= 1\n",
    "                if numc[c] >= 0 and numc[d] >= 0:\n",
    "                    l.append((c, d))\n",
    "                numc[c] += 1\n",
    "                numc[d] += 1\n",
    "        return l\n",
    "\n",
    "# s = Solution()\n",
    "# assert s.fourSum([1, 0, -1, 0, -2, 2], 0) == [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]\n",
    "# assert s.fourSum([1, 0, -1, 0, -2, 2], 1) == [[-2, 0, 1, 2], [-1, 0, 0, 2]]\n",
    "# assert s.fourSum([], 1) == []\n",
    "# assert s.fourSum([0, 0, 0, 0], 1) == []\n",
    "# assert s.fourSum([-3, -2, -1, 0, 0, 1, 2, 3], 0) == [[-3,-2,2,3],[-3,-1,1,3],[-3,0,0,3],[-3,0,1,2],[-2,-1,0,3],[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: 'List[int]', target: 'int') -> 'List[List[int]]':\n",
    "        res, dic = set(), {}\n",
    "        nums.sort()\n",
    "        length = len(nums)\n",
    "        \n",
    "        # 构建两数结果集\n",
    "        for i in range(length):\n",
    "            for j in range(i+1, length):\n",
    "                key = nums[i] + nums[j]\n",
    "                if key not in dic:\n",
    "                    dic[key] = [(i, j)]\n",
    "                else:\n",
    "                    dic[key].append((i, j))\n",
    "        \n",
    "        \n",
    "        for i in range(length):\n",
    "            for j in range(i+1, length-2):\n",
    "                index = target - nums[i] - nums[j]\n",
    "                if index in dic:\n",
    "                    for tmp in dic[index]:\n",
    "                        # 去除重复利用的情况\n",
    "                        if tmp[0] > j:\n",
    "                            # 对结果去重\n",
    "                            res.add((nums[i], nums[j], nums[tmp[0]], nums[tmp[1]]))\n",
    "        \n",
    "        return [list(i) for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = set()\n",
    "        dic = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i] + nums[j] not in dic:\n",
    "                    dic[nums[i]+nums[j]] = [(i,j)]\n",
    "                else:\n",
    "                    dic[nums[i]+nums[j]].append((i,j))\n",
    "        for p in range(len(nums)):\n",
    "            for q in range(p+1,len(nums)):\n",
    "                if target - nums[p] - nums[q] in dic:\n",
    "                    for each in dic[target-nums[p]-nums[q]]:\n",
    "                        i,j = each[0],each[1]\n",
    "                        if len({i,j,p,q}) == 4:\n",
    "                            temp = [nums[i],nums[j],nums[p],nums[q]]\n",
    "                            temp.sort()\n",
    "                            temp = tuple(temp)#元组可以被哈希，但是列表不可以\n",
    "                            # t1,t2,t3,t4 = temp\n",
    "                            # aa = (nums[t1],nums[t2],nums[t3],nums[t4])\n",
    "                            res.add(temp)\n",
    "        return [list(a) for a in res]\n",
    "                    \n",
    "                \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        nums.sort()\n",
    "        length = len(nums)\n",
    "\n",
    "        ij_dict = dict()\n",
    "        res_set = set()\n",
    "        for i in range(length - 1):\n",
    "            for j in range(i+1, length):\n",
    "\n",
    "                ij_sum = nums[i] + nums[j]\n",
    "                m = target - ij_sum\n",
    "                if m in ij_dict:\n",
    "                    for item in ij_dict[m]:\n",
    "                        if item[1] < i:\n",
    "                            res_set.add((nums[item[0]], nums[item[1]], nums[i], nums[j]))\n",
    "\n",
    "                if ij_sum not in ij_dict:\n",
    "                    ij_dict[ij_sum] = [(i, j)]\n",
    "                else:\n",
    "                    ij_dict[ij_sum].append((i, j))\n",
    "\n",
    "        return [[item[0], item[1], item[2], item[3]]for item in res_set]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        se,dic = set(),{}\n",
    "        nums.sort()\n",
    "        length = len(nums)\n",
    "        for i in range(length):\n",
    "            for j in range(i+1,length):\n",
    "                tt = nums[i] + nums[j]\n",
    "                if tt in dic.keys():\n",
    "                    dic[tt].append((i,j))\n",
    "                else:\n",
    "                    dic[tt] = [(i,j)]\n",
    "        for i in range(length):\n",
    "            for j in range(i+1,length-2):\n",
    "                tt = target - nums[i] - nums[j]\n",
    "                if tt in dic.keys():\n",
    "                    for p in dic[tt]:\n",
    "                        if p[0] > j:\n",
    "                            se.add((nums[i],nums[j],nums[p[0]],nums[p[1]]))\n",
    "        return [list(i) for i in se]\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        sum_dic = collections.defaultdict(list)\n",
    "        res_set = set()\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                sum_dic[nums[i]+nums[j]].append((i, j))\n",
    "        for key in sum_dic.keys():\n",
    "            left_key = target-key\n",
    "            if left_key in sum_dic.keys():\n",
    "                for (i, j) in sum_dic[key]:\n",
    "                    for (k, l) in sum_dic[left_key]:\n",
    "                        if i != k and i != l and j != k and j != l:\n",
    "                            res_set.add(tuple(sorted([nums[i], nums[j], nums[k], nums[l]])))\n",
    "        return list(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: 'List[int]', target: 'int') -> 'List[List[int]]':\n",
    "        nums.sort()\n",
    "        rlts = []\n",
    "        self.findNSum(nums,target,4,[],rlts)\n",
    "        return rlts\n",
    "    def findNSum(self,nums,target,N,rlt,rlts):\n",
    "        if len(nums)<N or N<2:\n",
    "            return\n",
    "        if N==2: #N=2的情况\n",
    "            l = 0 \n",
    "            r = len(nums)-1\n",
    "            while(l<r):\n",
    "                if nums[l] + nums[r] == target:\n",
    "                    rlts.append(rlt + [nums[l],nums[r]])\n",
    "                    r = r-1\n",
    "                    l = l+1\n",
    "                    while(l < r) and nums[l] == nums[l-1]:\n",
    "                        l = l+1\n",
    "                    while(l < r) and nums[r] == nums[r+1]:\n",
    "                        r = r-1\n",
    "                elif nums[l] + nums[r] < target:\n",
    "                    l = l+1\n",
    "                else:\n",
    "                    r = r-1\n",
    "        else:\n",
    "            for i in range(0,len(nums)-N+1):\n",
    "                #if target < nums[i]*N or target>nums[-1]*N: \n",
    "                 #   break\n",
    "                if i == 0 or (i!=0 and nums[i] != nums[i-1]):#去重\n",
    "                    self.findNSum(nums[i+1:],target-nums[i],N-1,rlt+[nums[i]],rlts)\n",
    "        return \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        numsLen = len(nums)\n",
    "        ret = []\n",
    "        if sum(nums[:4]) > target or numsLen < 4:\n",
    "            return []\n",
    "\n",
    "        for one in range(numsLen-3):\n",
    "            # 当值重复时，忽略\n",
    "            if one > 0 and nums[one] == nums[one-1]:\n",
    "                continue\n",
    "\n",
    "            min1 = nums[one] + nums[one+1] + nums[one+2] + nums[one+3]\n",
    "            # 数组4数和的最小值若大于目标值，其后没戏\n",
    "            if min1 > target:\n",
    "                continue\n",
    "\n",
    "            max1 = nums[one] + nums[numsLen-3] + nums[numsLen-2] + nums[numsLen-1]\n",
    "            # 数组4数和的最大值都小于目标值，没戏\n",
    "            if max1 < target:\n",
    "                continue\n",
    "\n",
    "            for two in range(one+1, numsLen-2):\n",
    "                if two > one+1 and nums[two] == nums[two-1]:\n",
    "                    continue\n",
    "                l = two + 1\n",
    "                r = numsLen - 1\n",
    "                min2 = nums[one] + nums[two] + nums[l] + nums[l+1]\n",
    "                if min2 > target:\n",
    "                    continue\n",
    "                max2 = nums[one] + nums[two] + nums[r-1] + nums[r]\n",
    "                if max2 < target:\n",
    "                    continue\n",
    "                while l < r:\n",
    "                    theSum = nums[one] + nums[two] + nums[l] + nums[r]\n",
    "                    if theSum == target:\n",
    "                        ret.append([nums[one], nums[two], nums[l], nums[r]])\n",
    "                        l += 1\n",
    "                        while l < r and nums[l] == nums[l-1]:\n",
    "                            l += 1\n",
    "                        r -= 1\n",
    "                        while l < r and nums[r] == nums[r+1]:\n",
    "                            r -= 1\n",
    "                    elif theSum < target:\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        r -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        output = []\n",
    "        for i in range(len(nums)):\n",
    "            if (i > 0 and nums[i] == nums[i - 1]):\n",
    "                continue\n",
    "            new_nums = nums[i + 1:]\n",
    "            new_target = target - nums[i]\n",
    "            a = self.threeSum(new_nums, new_target)\n",
    "            if (len(a) == 0):\n",
    "                continue\n",
    "            for k in a:\n",
    "                k.append(nums[i])\n",
    "                output.append(k)\n",
    "        return output\n",
    "                \n",
    "\n",
    "\n",
    "    def threeSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        output = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if (i > 0 and nums[i] == nums[i - 1]):\n",
    "                continue\n",
    "            curridx = i\n",
    "            leftidx = i + 1\n",
    "            rightidx = len(nums) - 1\n",
    "            while (leftidx < rightidx):\n",
    "                sum_ = nums[curridx] + nums[leftidx] + nums[rightidx]\n",
    "                if (sum_ == target):\n",
    "                    output.append([nums[leftidx], nums[curridx], nums[rightidx]])\n",
    "                    leftidx += 1\n",
    "                    while (leftidx < rightidx and nums[leftidx - 1] == nums[leftidx]):\n",
    "                        leftidx += 1\n",
    "                    rightidx -= 1\n",
    "                    while(leftidx < rightidx and nums[rightidx + 1] == nums[rightidx]):\n",
    "                        rightidx -= 1\n",
    "                elif (sum_ < target):\n",
    "                    leftidx += 1\n",
    "                elif (sum_ > target):\n",
    "                    rightidx -= 1\n",
    "            pre = nums[curridx]\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums, target):\n",
    "        nums.sort()\n",
    "        allres = []\n",
    "        for k in range(len(nums)-3):\n",
    "            if k > 0 and nums[k] == nums[k-1]:continue\n",
    "                \n",
    "            for j in range(k+1,len(nums)-2):                                 \n",
    "                l = j+1\n",
    "                r = len(nums)-1\n",
    "                \n",
    "                while l < r and j > k:\n",
    "                    res = sum([nums[k],nums[j],nums[l],nums[r]])\n",
    "                    \n",
    "                    if res > target:\n",
    "                        r -= 1\n",
    "                        while l < r and nums[r] == nums[r+1]: r -= 1\n",
    "                            \n",
    "                    elif res < target:\n",
    "                        l += 1\n",
    "                        while l < r and nums[l] == nums[l-1]: l += 1\n",
    "                            \n",
    "                    else:\n",
    "                        if [nums[k],nums[j],nums[l],nums[r]] not in allres:\n",
    "                            allres.append([nums[k],nums[j],nums[l],nums[r]])\n",
    "                            \n",
    "                        l += 1\n",
    "                        r -= 1\n",
    "                        while l < r and nums[r] == nums[r+1]: r -= 1\n",
    "                        while l < r and nums[l] == nums[l-1]: l += 1   \n",
    "                    \n",
    "        return allres "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        length = len(nums)\n",
    "        re = []\n",
    "        if length < 4:\n",
    "            return re\n",
    "        nums.sort()\n",
    "        for i in range(length - 3):\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                i += 1\n",
    "                continue\n",
    "            for j in range(i + 1, length - 2):\n",
    "                if j > i + 1 and nums[j] == nums[j - 1]:\n",
    "                    j += 1\n",
    "                    continue\n",
    "                p1, p2 = j + 1, length - 1\n",
    "                while p1 < p2:\n",
    "                    sum4 = nums[i] + nums[j] + nums[p1] + nums[p2]\n",
    "                    if sum4 == target:\n",
    "                        re.append([nums[i], nums[j], nums[p1], nums[p2]])\n",
    "                        while p1 < p2 and nums[p1] == nums[p1 + 1]:\n",
    "                            p1 += 1\n",
    "                        while p1 < p2 and nums[p2] == nums[p2 - 1]:\n",
    "                            p2 -= 1\n",
    "                        p1 += 1\n",
    "                        p2 -= 1\n",
    "                    elif sum4 < target:\n",
    "                        p1 += 1\n",
    "                    else:\n",
    "                        p2 -= 1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        if not nums or n < 4:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            a = nums[i]\n",
    "            if i > 0 and nums[i-1] == nums[i]:\n",
    "                continue\n",
    "            for j in range(i+1, n):\n",
    "                if j>i+1 and nums[j-1] == nums[j]:\n",
    "                    continue\n",
    "                b = nums[j]\n",
    "                if a + b * 3 > target:\n",
    "                    break\n",
    "                left = j+1\n",
    "                right = n-1\n",
    "                while left < right:\n",
    "                    if a + b + nums[left] + nums[right] == target:\n",
    "                        res.append([a, b, nums[left], nums[right]])\n",
    "                        while left < right and nums[left+1] == nums[left]:\n",
    "                            left += 1\n",
    "                        while left < right and nums[right-1] ==nums[right]:\n",
    "                            right -= 1\n",
    "                        left += 1\n",
    "                        right -= 1\n",
    "                    elif a + b + nums[left] + nums[right] < target:\n",
    "                        left += 1\n",
    "                    else:\n",
    "                        right -= 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        # 暴力法\n",
    "        # nums.sort()\n",
    "        # ret = []\n",
    "        # for i in range(len(nums)-3):\n",
    "        #     for j in range(i+1,len(nums)-2):\n",
    "        #         for m in range(j+1,len(nums)-1):\n",
    "        #             for n in range(m+1,len(nums)):\n",
    "        #                 if nums[i]+nums[j]+nums[m]+nums[n]==target:\n",
    "        #                     if [nums[i],nums[j],nums[m],nums[n]] not in ret:\n",
    "        #                         ret.append([nums[i],nums[j],nums[m],nums[n]])\n",
    "        # return ret\n",
    "        # 双指针法\n",
    "        # ret = []\n",
    "        # if len(nums)<4:\n",
    "        #     return ret\n",
    "        # nums.sort()\n",
    "        # for idi,i in enumerate(nums[:-3]):\n",
    "        #     if target>=0 and i>target:\n",
    "        #         break\n",
    "        #     if idi>0 and nums[idi]==nums[idi-1]:\n",
    "        #         continue\n",
    "        #     for idj,j in enumerate(nums[idi+1:-2]):\n",
    "        #         if target>=0 and i+j>target:\n",
    "        #             break\n",
    "        #         if idj>0 and nums[idi+1+idj]==nums[idi+1+idj-1]:\n",
    "        #             continue\n",
    "        #         l,r = idi+1+idj+1,len(nums)-1\n",
    "        #         while l<r:\n",
    "        #             s = i+j+nums[l]+nums[r]\n",
    "        #             if s==target:\n",
    "        #                 ret.append([i,j,nums[l],nums[r]])\n",
    "        #                 l+=1\n",
    "        #                 r-=1\n",
    "        #                 while l<r and nums[l]==nums[l-1]:l+=1\n",
    "        #                 while l<r and nums[r]==nums[r+1]:r-=1\n",
    "        #             elif s<target:\n",
    "        #                 l+=1\n",
    "        #                 while l<r and nums[l]==nums[l-1]:l+=1\n",
    "        #             else:\n",
    "        #                 r-=1\n",
    "        #                 while l<r and nums[r]==nums[r+1]:r-=1\n",
    "        # return ret\n",
    "        # 哈希法\n",
    "        hashset = {} # 用于验证重复值\n",
    "        ret = [] # 返回值\n",
    "        nums.sort()\n",
    "        temp_hash = {x:i for i,x in enumerate(nums)} # 哈希字典\n",
    "        for i,first in enumerate(nums[:-3]):\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            for j,second in enumerate(nums[i+1:-2]):\n",
    "                if j>0 and nums[i+j+1]==nums[i+j+1-1]:\n",
    "                    continue\n",
    "                for k,third in enumerate(nums[i+j+2:-1]):\n",
    "                    if k>0 and nums[i+j+k+2]==nums[i+j+k+2-1]:\n",
    "                        continue\n",
    "                    s = target-first-second-third\n",
    "                    if s in temp_hash:\n",
    "                        hash_index = temp_hash[s]\n",
    "                        if hash_index == i or hash_index==i+j+1 or hash_index==i+j+k+2:\n",
    "                            continue\n",
    "                        row = sorted([first,second,third,s])\n",
    "                        key = ','.join([str(x) for x in row])\n",
    "                        if key not in hashset:\n",
    "                            ret.append(row)\n",
    "                            hashset[key]=True\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        n=len(nums)\n",
    "        if n<4:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        for i in range(n-3):\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            for j in range(i+1,n-2):\n",
    "                if j>i+1 and nums[j]==nums[j-1]:\n",
    "                    continue\n",
    "                left,right=j+1,n-1\n",
    "                while left<right:\n",
    "                    four_sum=nums[i]+nums[j]+nums[left]+nums[right]\n",
    "                    if four_sum==target:\n",
    "                        res.append([nums[i],nums[j],nums[left],nums[right]])\n",
    "                        while left<right and nums[left]==nums[left+1]:\n",
    "                            left+=1\n",
    "                        left+=1\n",
    "                        while left<right and nums[right]==nums[right-1]:\n",
    "                            right-=1\n",
    "                        right-=1\n",
    "                    elif four_sum>target:\n",
    "                        right-=1\n",
    "                    else:\n",
    "                        left+=1\n",
    "        return res\n",
    "            \n",
    "                        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "            n = len(nums)\n",
    "            nums.sort()\n",
    "            ans = list()\n",
    "            # 枚举 a\n",
    "            for first in range(n):\n",
    "                if first > 0 and nums[first] == nums[first - 1]:\n",
    "                    continue\n",
    "                t = target - nums[first]\n",
    "                aa = self.threeSum(nums[first+1:], t)\n",
    "                if aa:\n",
    "                    for x in aa:\n",
    "                        ans.append([nums[first]] + x)\n",
    "            return ans\n",
    "\n",
    "    def threeSum(self, nums, t):\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = list()\n",
    "\n",
    "        # 枚举 a\n",
    "        for first in range(n):\n",
    "            # 需要和上一次枚举的数不相同\n",
    "            if first > 0 and nums[first] == nums[first - 1]:\n",
    "                continue\n",
    "            # c 对应的指针初始指向数组的最右端\n",
    "            third = n - 1\n",
    "            target = t-nums[first]\n",
    "            # 枚举 b\n",
    "            for second in range(first + 1, n):\n",
    "                # 需要和上一次枚举的数不相同\n",
    "                if second > first + 1 and nums[second] == nums[second - 1]:\n",
    "                    continue\n",
    "                # 需要保证 b 的指针在 c 的指针的左侧\n",
    "                while second < third and nums[second] + nums[third] > target:\n",
    "                    third -= 1\n",
    "                # 如果指针重合，随着 b 后续的增加\n",
    "                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环\n",
    "                if second == third:\n",
    "                    break\n",
    "                if nums[second] + nums[third] == target:\n",
    "                    ans.append([nums[first], nums[second], nums[third]])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not nums or len(nums) < 4:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)-3):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            for j in range(i+1,len(nums)-2):\n",
    "                if j > i+1 and nums[j] == nums[j-1]:\n",
    "                    continue\n",
    "                l,r = j+1,len(nums)-1\n",
    "                while l < r:\n",
    "                    if nums[i]+nums[j]+nums[l]+nums[r] == target:\n",
    "                        res.append([nums[i],nums[j],nums[l],nums[r]])\n",
    "                        while l < r and nums[l] == nums[l+1]:\n",
    "                            l += 1\n",
    "                        l += 1\n",
    "                        while l < r and nums[r] == nums[r-1]:\n",
    "                            r -= 1\n",
    "                        r -= 1\n",
    "                    elif nums[i]+nums[j]+nums[l]+nums[r] < target:\n",
    "                        while l < r and nums[l] == nums[l+1]:\n",
    "                            l += 1\n",
    "                        l += 1\n",
    "                    else:\n",
    "                        while l < r and nums[r] == nums[r-1]:\n",
    "                            r -= 1\n",
    "                        r -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        output = []\n",
    "        \n",
    "        def Search(i, target, oneSolution):\n",
    "\n",
    "            if target == 0 and len(oneSolution) == 4:  # 出口，找到正确的解了\n",
    "                output.append(oneSolution)\n",
    "                return\n",
    "            elif len(oneSolution) > 4 or i >= len(nums):  # 剪枝，超范围了\n",
    "                return\n",
    "            \n",
    "            if target - nums[i] - (3 - len(oneSolution)) * nums[-1] > 0:  # 当前这个数太小了\n",
    "                Search(i + 1, target, oneSolution)\n",
    "            elif target - (4 - len(oneSolution)) * nums[i] < 0:  # 当前组数的和太大了\n",
    "                return\n",
    "            else:  # 当前组数似乎没毛病\n",
    "                Search(i + 1, target, oneSolution)  # 不选这个数\n",
    "                Search(i + 1, target - nums[i], oneSolution + [nums[i]])  # 选这个数\n",
    "\n",
    "        Search(0, target, [])\n",
    "\n",
    "        output1 = []\n",
    "        output2 = []\n",
    "        for t in output:\n",
    "            if set(t) not in output1:\n",
    "                output1.append(set(t))\n",
    "                output2.append(t)\n",
    "\n",
    "        return output2\n",
    "\n",
    "# 作者：flying_du\n",
    "# 链接：https://leetcode-cn.com/problems/4sum/solution/python-wo-jiu-bu-yong-zhi-zhen-fa-zha-di-quan-guo-/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        len_nums = len(nums)\n",
    "\n",
    "        # hash后两个数的和，并保存索引\n",
    "        table = {}\n",
    "        for j in range(len_nums-1, 2, -1):\n",
    "            if j < len_nums-1 and nums[j] == nums[j+1]:\n",
    "                continue\n",
    "            if 4 * nums[j] < target:\n",
    "                break\n",
    "            if nums[j] + 3*nums[0] > target:\n",
    "                continue\n",
    "            for i in range(j-1, 1, -1):\n",
    "                if i < j-1 and nums[i] == nums[i+1]:\n",
    "                    continue\n",
    "                if nums[j] + 3*nums[i] < target:\n",
    "                    break\n",
    "                if nums[j] + nums[i] + 2*nums[0] > target:\n",
    "                    continue\n",
    "                table.setdefault(nums[i] + nums[j], []).append((i, j))\n",
    "\n",
    "        # 枚举前两个数\n",
    "        for i in range(len_nums-3):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            if nums[i] * 4 > target:\n",
    "                break\n",
    "            if nums[i] + 3 * nums[-1] < target:\n",
    "                continue\n",
    "            for j in range(i + 1, len_nums-2):\n",
    "                if j > i + 1 and nums[j] == nums[j-1]:\n",
    "                    continue\n",
    "                if nums[i] + 3*nums[j] > target:\n",
    "                    break\n",
    "                if nums[i] + nums[j] + 2*nums[-1] < target:\n",
    "                    continue\n",
    "                for index, jndex in table.get(target - nums[i] - nums[j], []):\n",
    "                    if j < index:\n",
    "                        ans.append([nums[i], nums[j], nums[index], nums[jndex]])\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        s = set()\n",
    "        for i in range(0, len(nums) - 3):\n",
    "            for j in range(i + 1, len(nums) - 2):\n",
    "                left = j + 1\n",
    "                right = len(nums) - 1\n",
    "                while left < right:\n",
    "                    if nums[i] + nums[j] + nums[left] + nums[right] < target:\n",
    "                        left += 1\n",
    "                    elif nums[i] + nums[j] + nums[left] + nums[right] > target:\n",
    "                        right -= 1\n",
    "                    else:\n",
    "                        s.add((tuple(sorted([nums[i], nums[j], nums[left], nums[right]]))))\n",
    "                        right -=1\n",
    "                        left += 1\n",
    "        return list(s)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        re = []\n",
    "        for i in range(n-3):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "\n",
    "            for j in range(i+1,n-2):\n",
    "                if j > i+1 and nums[j] == nums[j-1]:\n",
    "                    continue\n",
    "\n",
    "                x = j + 1\n",
    "                y = n - 1\n",
    "                while x < y:\n",
    "                    if x > j+1 and nums[x] == nums[x-1]:\n",
    "                        x = x + 1\n",
    "                        continue\n",
    "                    if y < n-1 and nums[y] == nums[y+1]:\n",
    "                        y = y - 1\n",
    "                        continue\n",
    "                    if nums[i]+nums[j]+nums[x]+nums[y] == target:\n",
    "                        re.append([nums[i], nums[j], nums[x], nums[y]])\n",
    "                        y = y - 1\n",
    "                        x = x + 1\n",
    "                    elif nums[i]+nums[j]+nums[x]+nums[y] > target:\n",
    "                        y = y - 1\n",
    "                    elif nums[i]+nums[j]+nums[x]+nums[y] < target:\n",
    "                        x = x + 1\n",
    "\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for k in range(0, n):\n",
    "            # if nums[k] > 0 and target > 0: break\n",
    "            if k > 0 and nums[k] == nums[k - 1]: continue\n",
    "            for i in range(k + 1, n):\n",
    "                # if nums[k] + nums[i] > 0 and target > 0: break\n",
    "                if i > k + 1 and nums[i] == nums[i - 1]: continue\n",
    "                left = i + 1\n",
    "                right = n - 1\n",
    "                while left < right:\n",
    "                    tmp = nums[k] + nums[i] + nums[left] + nums[right]\n",
    "                    if tmp > target: right -= 1\n",
    "                    elif tmp < target: left += 1\n",
    "                    else:\n",
    "                        res.append([nums[k], nums[i], nums[left], nums[right]])\n",
    "                        while left < right and nums[right] == nums[right - 1]: right -= 1\n",
    "                        while left < right and nums[left] == nums[left + 1]: left += 1\n",
    "                        left += 1\n",
    "                        right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(n-3):\n",
    "            for j in range(i+1, n-2):\n",
    "                target_ = target - nums[i] - nums[j]\n",
    "                left = j + 1\n",
    "                right = n - 1\n",
    "                while left < right:\n",
    "                    if target_ == (nums[left] + nums[right]):\n",
    "                        if [nums[i], nums[j], nums[left], nums[right]] not in res:\n",
    "                            res.append([nums[i], nums[j], nums[left], nums[right]])\n",
    "                        left += 1\n",
    "                        right -= 1\n",
    "                    elif target_ > (nums[left] + nums[right]):\n",
    "                        left += 1\n",
    "                    else:\n",
    "                        right -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        size = len(nums)\n",
    "        ans = []\n",
    "        if size < 4: return ans\n",
    "        nums = sorted(nums, reverse = True)\n",
    "        for a in range(size - 3):\n",
    "            if a > 0 and nums[a] == nums[a-1]:\n",
    "                continue\n",
    "            for b in range(a + 1,size - 2):\n",
    "                if b > a + 1 and nums[b] == nums[b-1]:\n",
    "                    continue\n",
    "                c = b + 1\n",
    "                d = size - 1\n",
    "                while c < d:\n",
    "\n",
    "                    if nums[a] + nums[b] + nums[c] + nums[d] > target:\n",
    "                        c += 1\n",
    "                    elif nums[a] + nums[b] + nums[c] + nums[d] < target:\n",
    "                        d -= 1\n",
    "                    else:\n",
    "                        ans.append([nums[a], nums[b], nums[c], nums[d]])\n",
    "                        c += 1\n",
    "                        d -= 1\n",
    "                        while c < d and nums[c] == nums[c-1]:\n",
    "                            c += 1\n",
    "                        while d < size - 1 and d > c and nums[d] == nums[d+1]:\n",
    "                            d -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict,Counter\n",
    "class Solution:\n",
    "    def fourSum(self, l: List[int], target: int) -> List[List[int]]:\n",
    "        # 考虑特殊情况\n",
    "        # 如果长度小于4，返回[]\n",
    "        if len(l) < 4:\n",
    "            return []\n",
    "        # 如果等于4，直接相加，是否等于target\n",
    "        if len(l) == 4:\n",
    "            if sum(l) == target:\n",
    "                return [l]\n",
    "            else:\n",
    "                return []\n",
    "        # 如果target 大于 4个大值之和，就返回[]\n",
    "        # 如果target 小于 4个小值之和，就返回[]\n",
    "        l1 = sorted(l)\n",
    "        if target > sum(l1[-4:]):\n",
    "            return []\n",
    "        if target < sum(l1[:4]):\n",
    "            return []\n",
    "\n",
    "        # 一般情况\n",
    "        # 去除一个元素重复多余4次的情况\n",
    "        c = Counter(l)\n",
    "        for k, v in c.items():\n",
    "            if v > 4:\n",
    "                c[k] = 4\n",
    "\n",
    "        # 重新连接成新的数组\n",
    "        l2 = []\n",
    "        for k, v in sorted(c.items(), key=lambda x: x[0]):\n",
    "            l2 += [k] * v\n",
    "\n",
    "        # print(c,l2)\n",
    "\n",
    "        # 定义记录结果的变量\n",
    "        result = []\n",
    "\n",
    "        # 定义一个递归获取的函数\n",
    "        def get(l2, target, p=[], n=0):\n",
    "\n",
    "            # for i,v in enumerate(l2):\n",
    "            #    if n+1 == 4: # 长度等于4，最后一个元素等于target就符合要求\n",
    "            #        if v == target:\n",
    "            #            r = p+[v]\n",
    "            #            if r not in result: # 避免重复\n",
    "            #                result.append(r)\n",
    "            #    else:\n",
    "            #        right = l2[i+1:]\n",
    "            #        if len(right) > 0: # 保证至少还有一个元素，再进入递归\n",
    "            #            get(right,target - v,p+[v],n+1)\n",
    "\n",
    "            for i in range(\n",
    "                len(l2) - 3,\n",
    "            ):\n",
    "                for j in range(i, len(l2)):\n",
    "                    min_ = sum(l2[i : i + 3]) + l2[j]\n",
    "                    max_ = l2[i] + sum(l2[j - 2 : j + 1])\n",
    "                    if not min_ <= target <= max_:\n",
    "                        continue\n",
    "                    else:\n",
    "                        middle = l2[i + 1: j]\n",
    "                        ii = 0\n",
    "                        jj = len(middle)-1\n",
    "                        while ii < jj :\n",
    "                            r = [l2[i],middle[ii],middle[jj],l2[j],]\n",
    "                            if sum(r)>target:\n",
    "                                jj -=1\n",
    "                            elif sum(r) < target:\n",
    "                                ii +=1\n",
    "                            else:\n",
    "                                while True and ii+1 < len(middle):\n",
    "                                    if middle[ii] != middle[ii+1]:\n",
    "                                        ii += 1\n",
    "                                        break\n",
    "                                    ii+=1\n",
    "                                while True and 0 <= jj-1:\n",
    "                                    if middle[jj] != middle[jj-1]:\n",
    "                                        jj -= 1\n",
    "                                        break\n",
    "                                    jj-=1\n",
    "                                if r not in result:\n",
    "                                    result.append(r)\n",
    "\n",
    "\n",
    "        get(\n",
    "            l2,\n",
    "            target,\n",
    "        )\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "    #分治法\n",
    "    #将问题分为若干子问题，对子问题求解后将解合并。\n",
    "    #先将四数和foursum分为；两数和，即twosum(a,threesum(A))，其中a是数组中的任意数，A是除a以外的其他数的集合；\n",
    "    #接下来继续对三数之和进行分解，即twosum(b,twosum(B))。这样就将四数之和转化为了两数之和问题\n",
    "        nums.sort()\n",
    "        results = []\n",
    "        self.findNsum(nums, target, 4, [], results)\n",
    "        return results\n",
    "\n",
    "    def findNsum(\n",
    "        self,\n",
    "        nums: List[int],\n",
    "        target: int,\n",
    "        N: int,\n",
    "        tempList: List[int],\n",
    "        results: List[List[int]],\n",
    "    ) -> None:\n",
    "        if len(nums) < N or N < 2:\n",
    "            return\n",
    "        if N == 2:\n",
    "            l = 0\n",
    "            r = len(nums) - 1\n",
    "            while l < r:\n",
    "                if nums[l] + nums[r] == target:\n",
    "                    results.append(tempList + [nums[l], nums[r]])\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                    # skip duplicated\n",
    "                    while l < r and nums[l] == nums[l - 1]:\n",
    "                        l += 1\n",
    "                    while r > l and nums[r] == nums[r + 1]:\n",
    "                        r -= 1\n",
    "                elif nums[l] + nums[r] < target:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        # 缩减问题规模\n",
    "        else:\n",
    "            for i in range(0, len(nums)):\n",
    "                # skip duplicated\n",
    "                if i == 0 or i > 0 and nums[i - 1] != nums[i]:\n",
    "                    self.findNsum(\n",
    "                        nums[i + 1 :],\n",
    "                        target - nums[i],\n",
    "                        N - 1,\n",
    "                        tempList + [nums[i]],\n",
    "                        results,\n",
    "                    )\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        if len(nums)<4:\n",
    "            return []\n",
    "        res=[]\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if i > 0 and nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if j > i+1 and nums[j]==nums[j-1]:\n",
    "                    continue\n",
    "                left=j+1\n",
    "                right=len(nums)-1\n",
    "                while left<right:\n",
    "                    if nums[i]+nums[j]+nums[left]+nums[right]<target:\n",
    "                        left+=1\n",
    "                    elif nums[i]+nums[j]+nums[left]+nums[right]> target:\n",
    "                        right-=1\n",
    "                    else:\n",
    "                        res.append([nums[i],nums[j],nums[left],nums[right]])\n",
    "                        left+=1\n",
    "                        right-=1\n",
    "                        while left < right and nums[left]==nums[left-1]:\n",
    "                            left+=1\n",
    "                        while left<right and nums[right]==nums[right+1]:\n",
    "                            right-=1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''n=len(nums)\n",
    "        if n <4:\n",
    "            return []\n",
    "        nums.sort()\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            if i>0 and nums[i]==nums[i-1]:\n",
    "                continue\n",
    "            for j in range(i+1,n):\n",
    "                if j >i+1 and nums[j]==nums[j-1]:\n",
    "                    continue\n",
    "                left=j+1\n",
    "                right=n-1\n",
    "                while left<right:\n",
    "                    sum_=nums[i]+nums[j]+nums[left]+nums[right]\n",
    "                    if sum_==target:\n",
    "                        res.append([nums[i],nums[j],nums[left],nums[right]])\n",
    "                        while left<right and nums[left]==nums[left+1]:\n",
    "                            left+=1\n",
    "                        while left<right and nums[right]==nums[right-1]:\n",
    "                            right-=1\n",
    "                        left+=1\n",
    "                        right-=1\n",
    "                    elif sum_<target:\n",
    "                        left+=1\n",
    "                    else:\n",
    "                        right-=1\n",
    "        return res'''\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        res = []\n",
    "        for i in range(n-3):\n",
    "            if i>0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            real_target = target - nums[i]\n",
    "            for j in range(i+1,n-2):\n",
    "                if j > i+1  and nums[j] == nums[j-1]:\n",
    "                    continue\n",
    "                \n",
    "                start = j+1\n",
    "                end = n-1\n",
    "                while start < end:\n",
    "                    tmp = nums[j]+nums[start]+nums[end]\n",
    "                    if tmp == real_target:\n",
    "                        res.append([nums[i],nums[j],nums[start],nums[end]])\n",
    "                        start +=1\n",
    "                        end -=1 \n",
    "                        while start< end and nums[start] == nums[start-1]:\n",
    "                            start +=1\n",
    "                        while start <end and nums[end] ==  nums[end+1]:\n",
    "                            end -= 1\n",
    "                    elif tmp < real_target:\n",
    "                        start +=1\n",
    "                        while start< end and nums[start] == nums[start-1]:\n",
    "                            start +=1\n",
    "                    else:\n",
    "                        end -=1 \n",
    "                        while start <end and nums[end] ==  nums[end+1]:\n",
    "                            end -= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        if not nums or len(nums) < 4:\n",
    "            return ans\n",
    "        nums.sort()\n",
    "        for i in range(len(nums) - 3):\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:\n",
    "                break\n",
    "            if nums[i] + nums[len(nums) - 1] + nums[len(nums) - 2] + nums[len(nums) - 3] < target:\n",
    "                continue\n",
    "            for j in range(i + 1, len(nums) - 2):\n",
    "                if j > i + 1 and nums[j] == nums[j - 1]:\n",
    "                    continue\n",
    "                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:\n",
    "                    break\n",
    "                if nums[i] + nums[j] + nums[len(nums) - 2] + nums[len(nums) - 1] < target:\n",
    "                    continue\n",
    "                left, right = j + 1, len(nums) - 1\n",
    "                while left < right:\n",
    "                    s = nums[i] + nums[j] + nums[left] + nums[right]\n",
    "                    if s == target:\n",
    "                        ans.append([nums[i], nums[j], nums[left], nums[right]])\n",
    "                        while left < right and nums[left] == nums[left + 1]:\n",
    "                            left += 1\n",
    "                        left += 1\n",
    "                        while left < right and nums[right] == nums[right - 1]:\n",
    "                            right -= 1\n",
    "                        right -= 1\n",
    "                    elif s < target:\n",
    "                        left += 1\n",
    "                    else:\n",
    "                        right -= 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
